//
// Created by liushuai on 18-8-20.
//
#include <iostream>
#include <boost/timer.hpp>
using namespace std;
using namespace boost;
int MaxSum1(int i, int j){
    int matrix[5][5] = {{7,0,0,0,0},{3,8,0,0,0},{8,1,0,0,0},{2,7,4,4,0},{2,5,2,6,5}};
    for(int i=3;i>=0;i--)
    {
        for(int j=0;j<3;j++)
            matrix[4][j] = matrix[i][j]+max(matrix[4][j],matrix[4][j+1]);
    }
    return matrix[4][0];
}
//存储计算值，不用迭代
int MaxSum(int i, int j){
    int matrix[5][5] = {{7,0,0,0,0},{3,8,0,0,0},{8,1,0,0,0},{2,7,4,4,0},{2,5,2,6,5}};
    for(int i=3;i>=0;i--)
    {
        for(int j=0;j<3;j++)
            matrix[i][j] = matrix[i][j]+max(matrix[i+1][j],matrix[i+1][j+1]);
    }
    return matrix[0][0];
}
int max_value(int i,int j)
{
    int matrix[5][5] = {{7,0,0,0,0},{3,8,0,0,0},{8,1,0,0,0},{2,7,4,4,0},{2,5,2,6,5}};
    int r;
    if(i==4)
        return matrix[i][j];
    else
    {
        int x,y,m;
        x = matrix[i+1][j];
        y = matrix[i+1][j+1];
        m = max(x,y);
        r = m+max_value(i+1,j);
//        cout<<"Max value: "<<r<<endl;
        cout<<"Max value: "<<r<<endl;
        return r;
    }
}
int main()
{
    timer t;
    cout<<MaxSum1(0,0)<<endl;
    cout<<"流失时间:"<<t.elapsed()<<endl;
}